using System;
using System.Collections.Generic;
using System.Reflection;
using Xunit;

namespace LeetCodeQuestionBank.Algorithm
{
    public class No0456_Find132pattern
    {
        /*
        给定一个整数序列：a1, a2, ..., an，
        一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak < aj。
        设计一个算法，当给定有 n 个数字的序列时，验证这个序列中是否含有132模式的子序列。
        注意：n 的值小于15000。

        示例1:
            输入: [1, 2, 3, 4]
            输出: False
            解释: 序列中不存在132模式的子序列。

        示例 2:
            输入: [3, 1, 4, 2]
            输出: True
            解释: 序列中有 1 个132模式的子序列： [1, 4, 2].

        示例 3:
            输入: [-1, 3, 2, 0]
            输出: True
            解释: 序列中有 3 个132模式的的子序列: [-1, 3, 2], [-1, 3, 0] 和 [-1, 2, 0].
        */

        public static IEnumerable<object[]> GetTestArgs()
        {
            return new object[][] {
                new object[] { false, new int[] { 1, 2, 3, 4 }, },
                new object[] { true, new int[] { 3, 1, 4, 2 }, },
                new object[] { true, new int[] { -1, 3, 2, 0 }, },
                new object[] { true, new int[] { 3, 5, 0, 3, 4 }, },
            }.MergeFuncNames(new string[] {
                nameof(Find132pattern),
            });
        }

        [Theory]
        [MemberData(nameof(GetTestArgs))]
        public void TestFunc_Find132pattern(string funcName, bool result, int[] inputs)
        {
            Type type = this.GetType();
            MethodInfo methodInfo = type.GetMethod(funcName);
            bool methodResult = (bool)methodInfo.Invoke(this, new object[] { inputs });
            Assert.Equal(result, methodResult);
        }

        public bool Find132pattern(int[] nums)
        {
            int n = nums.Length;
            Stack<int> candidateK = new Stack<int>();
            candidateK.Push(nums[n - 1]);
            int maxK = int.MinValue;
            for (int i = n - 2; i >= 0; --i)
            {
                if (nums[i] < maxK)
                {
                    return true;
                }
                while (candidateK.Count > 0 && nums[i] > candidateK.Peek())
                {
                    maxK = candidateK.Pop();
                }
                if (nums[i] > maxK)
                {
                    candidateK.Push(nums[i]);
                }
            }
            return false;
        }
    }
}
